congruence

Definition

• Context:
  • A monoid \(\mathcal{M}: (M, e, *)\)
• A congruence on \(\mathcal{M}\) is an equivalence relation \(\sim\) on \(\mathcal{M}\) such that \(\forall m, m', n, n' \in \mathcal{M}\), if \(m \sim m'\) and \(n \sim n'\), then \(m * n \sim n' \sim m'\)
• An equivalence relation that interacts well with the multiplication formula of a monoid is called a congruence on that monoid

Equivalence relation

• for a set \(X\), an equivalence relation on it is a subset \(R \subseteq X \times X\) that satisfies reflexivity, symmetry, and transitivity

Path Equivalence Declaration (PED)

• Context:
  • let \(G = (V, A, src, tgt)\) be a graph
  • let \(\text{Path}_G\) denote the set of paths in \(G\)
• A PED is an expression of the form \(p \simeq q\), where \(src(p) = src(q)\) and \(tgt(p) = tgt(q)\)
• A congruence on G is a relation \(\simeq\) on \(\text{Path}_G\) that has the following properties
  • it's an equivalence relation
  • if \(p \simeq q\) then \(src(p) = src(q)\)
  • if \(p \simeq q\) then \(tgt(p) = tgt(q)\)
• Any set of path equivalence declarations (PEDs) generates a congruence

reference:

• Category Theory for the Sciences]